package 小米笔试题;
//dfs算法
// https://www.nowcoder.com/questionTerminal/14bcbcb7ae3c40c9bdbc5a0861361c29
public class 小米相邻单词搜索0902 {
    //人生中第一个自己做出来的DFS算法

        public static int k=0;
        public static boolean exist(char[][] board, String word) {
            int m = board.length;
            System.out.println(m);
            int n = board[0].length;
            System.out.println(n);
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; i++)
                for (int j = 0; j <n ; j++) {
                    if (dfs(board,i,j,word,k,visited))
                        return true;
                }
            return false;
        }

        private static boolean dfs(char[][] board, int i, int j, String word, int kth,boolean[][] visited) {
            if (kth>=word.length())
                return true;
            if (i>=0 && i<board.length && j>=0 && j<board[0].length && !visited[i][j] && word.charAt(kth)==board[i][j]){
                visited[i][j]=true;
                kth++;
                if (dfs(board,i,j+1,word,kth,visited) ||(dfs(board,i+1,j,word,kth,visited)||(dfs(board,i,j-1,word,kth,visited))||(dfs(board,i-1,j,word,kth,visited))))
                    return true;
                visited[i][j] = false;//注意这里需要置为false
            }
            return false;
        }

        public static void main(String[] args) {
            char[][] board = {{'C','A','A'},{'A','A','A'},{'B','C','D'}};
            //char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
            String word = "AAB";
            System.out.println(exist(board,word));
        }
    }


